//
// Created by francklinson on 2021/8/23 AT 10:12.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>

using namespace std;

class Solution {
public:
    int getMaximumGenerated(int n) {
        vector<int> nums{0, 1};
        if (n <= 1) {
            return nums[n];
        }
        for (int k = 2; k <= n; ++k) {
            if (k % 2 == 0)
                nums.push_back(nums[k / 2]);
            else
                nums.push_back(nums[k / 2] + nums[k / 2 + 1]);
        }
        return *max_element(nums.begin(), nums.end());
    }
};

class Solution2 { // 题解
public:
    int getMaximumGenerated(int n) {
        if (n == 0) {
            return 0;
        }
        vector<int> nums(n + 1);
        nums[1] = 1;
        for (int i = 2; i <= n; ++i) {
            nums[i] = nums[i / 2] + i % 2 * nums[i / 2 + 1];
        }
        return *max_element(nums.begin(), nums.end());
    }
};

int main() {
    Solution solution;
    cout << solution.getMaximumGenerated(6) << endl;
    cout << solution.getMaximumGenerated(0) << endl;
    cout << solution.getMaximumGenerated(1) << endl;
    return 0;
}

